#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <iostream>
using namespace std;

class matrix{
  int a[2][2];
 
public:
  matrix(){a[0][0]=0;a[0][1]=a[1][0]=a[1][1]=1; }
  matrix operator*(const matrix m){
    int b[2][2];
    for(int i=0; i<2; ++i)//row
      for(int j=0; j<2; ++j){//column
	b[i][j] = 0;
	for(int k=0; k<2; ++k)
	  b[i][j] += a[i][k]*m.a[k][j];
      }
    for(int i=0; i<2; ++i)//row
      for(int j=0; j<2; ++j)//column
	a[i][j] = b[i][j];
    return *this;
  }
  int select(int i,int j){return a[i][j];}


  friend ostream& operator<<(ostream& os, matrix& m);
};
matrix get(int i){
  if(i == 1)
    return matrix();
  matrix tmp = get(i/2);
  if(i%2 == 0)
    return tmp*tmp;
  else
    return tmp*tmp*matrix();
}
ostream& operator<<(ostream& os, matrix& m){
  os<<m.a[0][0]<<"\t"<<m.a[0][1]<<endl;
  os<<m.a[1][0]<<"\t"<<m.a[1][1]<<endl;
  return os;
}

int fib(int n)
{
  if(n<=1)
    return n;
  else{
    matrix m = get(n);
    return m.select(0,1);
  }
}

int main(int argc, char *argv[])
{
  int n;
  //initialize n
  if(argc == 2){
    n = atoi(argv[1]);
  }
  else{
    puts("usage: fib n");
    return 1;
  }
  assert(n>=0);
  printf("fib(%d) is %d\n",n, fib(n) ) ;
  return 0;
}
